package com.algorithm;

import java.util.Arrays;
import java.util.Hashtable;
import java.util.Queue;
import java.util.concurrent.ConcurrentLinkedQueue;

import cn.hutool.core.util.StrUtil;

/**
 * <pre>
 * 广度优先搜索 -- 非加权图
 *  1、广度优先搜索指出是否有从A到B的路径；
 *  2、如果有，广度优先将找出最短的路径；
 *  3、你需要按加入的顺序检测搜索列表中的人，否则找到的就不是最短路径，因此搜索列表必须是队列；
 *  4、检查过的人，务必不要再去检查，否则可能导致无限循环；
 * </pre>
 */
class BreadthFirstSearch {
    public static void main(String[] args) {
        /*
        实现图
         */
        Hashtable<String, String[]> graph = new Hashtable<String, String[]>();
        graph.put("you", new String[]{"alice", "bob", "claire"});
        graph.put("bob", new String[]{"you", "anuj", "peggy"});
        graph.put("alice", new String[]{"you", "peggy"});
        graph.put("claire", new String[]{"you", "thom", "jonny"});
        graph.put("anuj", new String[]{"bob"});
        graph.put("peggy", new String[]{"bob", "alice"});
        graph.put("thom", new String[]{"claire"});
        graph.put("jonny", new String[]{"claire"});

        System.out.println(BreadthFirstSearch.breadthFirstSearch(graph, "you"));
    }

    private static String breadthFirstSearch(Hashtable<String, String[]> graph, String youName) {
           /*
        搜索队列--先进先出
         */
        Queue<String> queue = new ConcurrentLinkedQueue<String>(Arrays.asList(graph.get(youName)));
        /*
        已经检查过的--防止无限循环
         */
        Hashtable<String, Boolean> searched = new Hashtable<String, Boolean>();

        while ((queue.peek()) != null) {
            String people = queue.poll();
            if (searched.get(people) == null) {
                if (people.endsWith("m")) { //简单的以此为需要找到的人
                    return StrUtil.format("{} 会手写广度优先搜索！", people);
                } else {
                    queue.addAll(Arrays.asList(graph.get(people)));
                }
            }
            searched.put(people, true);
        }

        return "你的人际关系网中没人会手写广度优先搜索";
    }
}